package cn.pugle.oj.base;

import cn.pugle.oj.leetcode.TreeNode;

import java.util.LinkedList;

/**
 * {@link #dfsPre0} 深度-前序-递归 LC144
 * {@link #dfsPre1} 深度-前序-循环 栈
 * <p>
 * {@link #dfsMid0} 深度-中序-递归 LC94
 * {@link #dfsMid1} 深度-中序-循环 俩栈, 来回遍历的奇怪写法
 * {@link #dfsMid2} 深度-中序-循环 一个栈, 类似递归, 用栈模拟递归
 * <p>
 * {@link #dfsPost0} 深度-后序-递归 LC145
 * {@link #dfsPost1} 深度-后序-循环 俩栈, 类似前序+栈, 第二个栈用于将结果倒置过来
 * {@link #dfsPost2} 深度-后序-循环 一个栈, 类似递归, 用栈模拟递归, 但是栈里除了node还得有个标记
 * <p>
 * {@link #bfs0} 广度-层次-循环 队列, LC102, 另见LC117, 加next指针指向右邻居
 *
 * @author tzp
 * @since 2020/9/17
 */
@SuppressWarnings({"ALL", "AlibabaSwitchStatement"})
public class TreeTravel {
    public static void dfsPre0(TreeNode root) {
        System.out.print(root.val + " ");
        if (root.left != null) {
            dfsPre0(root.left);
        }
        if (root.right != null) {
            dfsPre0(root.right);
        }
    }

    public static void dfsPre1(TreeNode root) {
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        linkedList.addLast(root);
        while (linkedList.size() != 0) {
            TreeNode cur = linkedList.pollLast();
            System.out.print(cur.val + " ");
            if (cur.right != null) linkedList.addLast(cur.right);
            if (cur.left != null) linkedList.addLast(cur.left);
        }
    }

    public static void dfsMid0(TreeNode root) {
        if (root.left != null) {
            dfsMid0(root.left);
        }
        System.out.print(root.val + " ");
        if (root.right != null) {
            dfsMid0(root.right);
        }
    }

    public static void dfsMid1(TreeNode root) {
        LinkedList<TreeNode> linkedList1 = new LinkedList<>();
        LinkedList<TreeNode> linkedList2 = new LinkedList<>();
        linkedList1.addLast(root);
        while (linkedList1.size() != 0 || linkedList2.size() != 0) {
            TreeNode cur = linkedList1.pollLast();
            if (cur != null) {
                if (cur.left != null) {
                    linkedList2.addLast(cur);
                    linkedList1.addLast(cur.left);
                } else {
                    System.out.print(cur.val + " ");
                    if (cur.right != null) linkedList1.addLast(cur.right);
                }
            } else {
                cur = linkedList2.pollLast();
                System.out.print(cur.val + " ");
                if (cur.right != null) linkedList1.addLast(cur.right);
            }
        }
    }

    public static void dfsMid2(TreeNode root) {
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        TreeNode cur = root;
        while (linkedList.size() != 0 || cur != null) {
            if (cur != null) {
                linkedList.addLast(cur);
                cur = cur.left;
            } else {
                cur = linkedList.removeLast();
                System.out.print(cur.val + " ");
                cur = cur.right;
            }
        }
    }

    public static void dfsPost0(TreeNode root) {
        if (root.left != null) {
            dfsPost0(root.left);
        }
        if (root.right != null) {
            dfsPost0(root.right);
        }
        System.out.print(root.val + " ");
    }

    public static void dfsPost1(TreeNode root) {
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        LinkedList<TreeNode> result = new LinkedList<>();
        linkedList.addLast(root);
        while (linkedList.size() != 0) {
            TreeNode cur = linkedList.pollLast();
            if (cur.left != null) linkedList.addLast(cur.left);
            if (cur.right != null) linkedList.addLast(cur.right);
            result.addLast(cur);
        }
        while (result.size() != 0) {
            System.out.print(result.pollLast().val + " ");
        }
    }

    public static class Pair<A, B> {
        public A a;
        public B b;

        public Pair(A a, B b) {
            this.a = a;
            this.b = b;
        }
    }

    //不像dfsMid2那么简单哦, dfsMid的栈里只存cur, 第一次取出后直接就丢了, 因为后面用不上
    //但是在dfsPost中, 栈里的cur放进去之后要取出两次.
    public static void dfsPost2(TreeNode root) {
        LinkedList<Pair<TreeNode, Integer>> linkedList = new LinkedList<>();
        linkedList.addLast(new Pair<>(root, 0));
        Pair<TreeNode, Integer> cur;
        while (linkedList.size() != 0) {
            cur = linkedList.getLast();
            switch (cur.b) {
                case 0: {
                    if (cur.a.left != null) {
                        cur.b = 1;
                        linkedList.addLast(new Pair<>(cur.a.left, 0));
                        break;
                    }
                }
                case 1: {
                    if (cur.a.right != null) {
                        cur.b = 2;
                        linkedList.addLast(new Pair<>(cur.a.right, 0));
                        break;
                    }
                }
                case 2: {
                    linkedList.removeLast();
                    System.out.print(cur.a.val + " ");
                }
            }
        }
    }

    public static void bfs0(TreeNode treeNode) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(treeNode);
        TreeNode seperator = treeNode;//分层用
        while (queue.size() != 0) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);

            if (node == seperator && queue.size() != 0) {
                seperator = queue.getLast();
            }
        }
    }

    public static void main(String[] args) {
        Integer[] a = {1, 2, 4, 3, 5, 7, 10, 6, null, 8, null, 11, 9, 15, null, null, null, 12, null, null, null, 13, null, null, null, null, 14};
        TreeNode treeNode = TreeNode.arrayToTreeNode(a);

//        bfs0(treeNode);
//        System.out.println("");
//
//        dfsPre0(treeNode);
//        System.out.println("");
//
//        dfsPre1(treeNode);
//        System.out.println("");
//
//        dfsMid0(treeNode);
//        System.out.println("");
//
//        dfsMid1(treeNode);
//        System.out.println("");
//
//        dfsMid2(treeNode);
//        System.out.println("");

        dfsPost0(treeNode);
        System.out.println("");
//
        dfsPost1(treeNode);
        System.out.println("");

        dfsPost2(treeNode);
        System.out.println("");
    }
}
